package com.linzm.leetcode.primary.exercises3_20230122;

import java.util.Arrays;

/**
 * @Author zimingl
 * @Date 2023/1/24 22:43
 * @Description: 宝石补给
 */
public class Demo17_50 {
    /**
     * 欢迎各位勇者来到力扣新手村，在开始试炼之前，请各位勇者先进行「宝石补给」。
     * 每位勇者初始都拥有一些能量宝石， gem[i] 表示第 i 位勇者的宝石数量。现在这些勇者们进行了一系列的赠送，operations[j] = [x, y] 表示在第 j 次的赠送中 第 x 位勇者将自己一半的宝石（需向下取整）赠送给第 y 位勇者。
     * 在完成所有的赠送后，请找到拥有最多宝石的勇者和拥有最少宝石的勇者，并返回他们二者的宝石数量之差。
     * 输入：gem = [100,0,50,100], operations = [[0,2],[0,1],[3,0],[3,0]]
     *
     * 输出：75
     *
     * 解释： 第 1 次操作，勇者 0 将一半的宝石赠送给勇者 2， gem = [50,0,100,100] 第 2 次操作，勇者 0 将一半的宝石赠送给勇者 1， gem = [25,25,100,100] 第 3 次操作，勇者 3 将一半的宝石赠送给勇者 0，
     * gem = [75,25,100,50] 第 4 次操作，勇者 3 将一半的宝石赠送给勇者 0， gem = [100,25,100,25] 返回 100 - 25 = 75
     */
    public static void main(String[] args) {
        int[] gem = {100,0,50,100};
        int[][] operations = {{0,2},{0,1},{3,0},{3,0}};
        Demo17_50 demo17_50 = new Demo17_50();
        int giveGem = demo17_50.giveGem(gem, operations);
        System.out.println(giveGem);
    }

    private int giveGem(int[] gem, int[][] operations) {
        for (int i = 0; i < operations.length; i++) {
            int tmp = gem[operations[i][0]];
            gem[operations[i][0]] = gem[operations[i][0]] - tmp / 2;
            gem[operations[i][1]] = gem[operations[i][1]] + tmp / 2;
        }
        Arrays.sort(gem);
        return Math.abs(gem[0] - gem[gem.length - 1]);
    }
}
